/**
 * 我是想着第一层往右走，走到比target大的值，i+1;第二层往左走，走到比target小的值，i+1；循环直到找到target。并没有超时
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    let row = matrix.length,
        column = matrix[0].length,
        curCol = 0,
        val;

    for (let i = 0; i < row; i++) {
        val = matrix[i][curCol]
        if (val < target) {
            while (curCol < column - 1 && val < target) {
                val = matrix[i][++curCol]
            }
            if (val === target) return true
            continue
        }

        if (val > target) {
            while (curCol > 0 && val > target) {
                val = matrix[i][--curCol]
            }
            if (val === target) return true
            continue
        }
        if (val === target) return true
    }

    return false
};


/**
 * 看到官解，是可以从第一层就往左走的，右边列的值都比target大，精简如下
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    let row = matrix.length,
        curCol = matrix[0].length - 1,
        val;

    for (let i = 0; i < row; i++) {
        val = matrix[i][curCol]
        while (curCol > 0 && val > target) {
            val = matrix[i][--curCol]
        }
        if (val === target) return true
        if (curCol === 0 && val > target) break
    }

    return false
};




/**
 * 官解
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let x = 0, y = n - 1;
    while (x < m && y >= 0) {
        if (matrix[x][y] === target) {
            return true;
        }
        if (matrix[x][y] > target) {
            --y;
        } else {
            ++x;
        }
    }
    return false;
};